package com.leetcode.problems005;


/**
 * @Description
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution2 {

    /**
     *s[i,j]区间内是否为回文字符串
     * dp[i][j] = s[i] == s[j] and (dp[i+1][j-1] or i-j < 3[如果i,j字符相等，小于3的长度，都为回文])
     */
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1){
            return s;
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i = 0; i < s.length();i++){
            dp[i][i] = true;
        }
        for(int i = 1; i < s.length();i++){
            dp[i][0] = false;
        }
        int maxLen = 1;
        int start = 0;
        for (int j = 1; j < s.length();j++) {
            for (int i = 0; i < j; i++) {
                if(s.charAt(i) != s.charAt(j)){
                    dp[i][j] = false;
                    continue;
                }
                if(j - i < 3 || dp[i + 1][j - 1]){
                    dp[i][j] = true;
                    if(j -i + 1 > maxLen){
                        maxLen = j - i + 1;
                        start = i;
                    }
                }
            }
        }


        return s.substring(start, start + maxLen);
    }


    public static void main(String[] args) {
        System.out.println(new Solution2().longestPalindrome("ac"));
    }
}
